package topcoder;

import org.junit.Test;

public class BinaryCode {

	@Test
	public void test() {
		BinaryCode t = new BinaryCode();
		String[] r = t.decode("12221112222221112221111111112221111");
		for (String s : r) {
			System.out.println(s);
		}
	}

	public int[] toIntArray(String str) {
		int[] r = new int[str.length()];
		for (int i = 0; i < str.length(); ++i) {
			r[i] = Character.getNumericValue(str.charAt(i));
		}
		return r;
	}

	public String toStr(int[] arr) {
		char[] chs = new char[arr.length];
		for (int i = 0; i < arr.length; ++i)
			chs[i] = Character.forDigit(arr[i], 10);
		return new String(chs);
	}

	public String[] decode(String message) {
		if (message == null || message.length() == 0)
			return null;

		if (message.length() == 1) {
			if (message.charAt(0) == '0')
				return new String[] { message, "NONE" };
			else if (message.charAt(0) == '1')
				return new String[] { "NONE", message };
			else
				return new String[] { "NONE", "NONE" };
		}

		int[] chs = toIntArray(message);
		int[] r1 = new int[chs.length];
		int[] r2 = new int[chs.length];
		r1[0] = 0;
		r2[0] = 1;

		int i = 1;
		for (; i < chs.length; ++i) {
			r1[i] = chs[i - 1] - r1[i - 1];
			if (r1[i] > 1 || r1[i] < 0) {
				break;
			} else {
				chs[i] = chs[i] - r1[i - 1];
				if (i == chs.length - 1 && chs[i] != r1[i])
					break;
			}
		}

		String s1;
		if (i < chs.length)
			s1 = "NONE";
		else
			s1 = toStr(r1);

		chs = toIntArray(message);
		i = 1;
		for (; i < chs.length; ++i) {
			r2[i] = chs[i - 1] - r2[i - 1];
			if (r2[i] > 1 || r2[i] < 0) {
				break;
			} else {
				chs[i] = chs[i] - r2[i - 1];
				if (i == chs.length - 1 && chs[i] != r2[i])
					break;
			}
		}

		String s2;
		if (i < chs.length)
			s2 = "NONE";
		else
			s2 = toStr(r2);

		String[] result = new String[2];
		result[0] = s1;
		result[1] = s2;
		return result;
	}
}
